{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Fixed Point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fixedPoint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不动点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定已经按 <strong>升序</strong> 排列、由不同整数组成的数组 <code>arr</code>，返回满足 <code>arr[i] == i</code> 的最小索引 <code>i</code>。如果不存在这样的 <code>i</code>，返回 <code>-1</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [-10,-5,0,3,7]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>对于给定的数组，<code>arr[0] = -10，arr[1] = -5，arr[2] = 0，arr[3] = 3</code>，因此输出为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,2,5,8,17]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong><code>arr[0] = 0</code>，因此输出为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [-10,-5,3,4,7,9]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>不存在这样的 i 满足 <code>arr[i] = i</code>，因此输出为 -1 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length < 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> <= arr[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>时间复杂度为 <code>O(n)</code> 的解决方案很直观也很简单。你可以设计更优的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fixed-point](https://leetcode.cn/problems/fixed-point/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fixed-point](https://leetcode.cn/problems/fixed-point/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-10,-5,0,3,7]', '[0,2,5,8,17]', '[-10,-5,3,4,7,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i, x in enumerate(arr):\n",
    "            if i == x:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        l, r = 0, len(arr) - 1\n",
    "\n",
    "        while l < r:\n",
    "\n",
    "\n",
    "            mid = ( l + r ) // 2\n",
    "\n",
    "            if arr[mid] >= mid:\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l if arr[l] == l else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == i:\n",
    "                return i \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        idx = 0\n",
    "        while idx < len(arr):\n",
    "            if arr[idx] == idx:\n",
    "                return idx\n",
    "            elif arr[idx] > idx:\n",
    "                return -1\n",
    "            idx = idx + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] == i:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i,j in enumerate(arr):\n",
    "            if i == j:\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for n , i in enumerate(arr):\n",
    "            if n == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i, num in enumerate(arr):\n",
    "            if num == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if arr[i]==i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        return min((i  for i, num in enumerate(arr) if num == i), default=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i,j in enumerate(arr):\n",
    "            if i == j:\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i, v in enumerate(arr):\n",
    "            if i == v:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        return min((i  for i, num in enumerate(arr) if num == i), default=-1)\n",
    "        \n",
    "        # left,right = 0,len(arr)-1\n",
    "        # m = float('inf')\n",
    "        # while left <= right:\n",
    "        #     middle = left + (right - left)//2\n",
    "        #     if arr[middle] < middle :\n",
    "        #         left = middle + 1\n",
    "        #     elif arr[middle] >= middle:\n",
    "        #         if arr[middle] == middle:\n",
    "        #             m = min(middle,m)\n",
    "        #         right = middle - 1\n",
    "           \n",
    "        # if m != float('inf') :\n",
    "        #     return m\n",
    "        # else:\n",
    "        #     return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if arr[mid] >= mid:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left if arr[left] == left else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if i == arr[i]:\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if i == arr[i]:\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        idx = 0\n",
    "        while idx < len(arr):\n",
    "            if arr[idx] == idx:\n",
    "                return idx\n",
    "            idx = idx + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        l,r = 0,len(arr)-1\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if mid <= arr[mid]:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        if arr[l]==l:return l\n",
    "        else:return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right :\n",
    "            middle = (left + right) // 2\n",
    "            if arr[middle] == middle:\n",
    "                if (middle == 0) or (arr[middle-1] != middle-1):\n",
    "                    return middle\n",
    "                else:\n",
    "                    right = middle - 1\n",
    "            elif arr[middle] > middle:\n",
    "                right = middle - 1\n",
    "            else :\n",
    "                left = middle + 1            \n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        L, R = 0, len(arr)-1\n",
    "        ans = -1\n",
    "        while L <= R:\n",
    "            mid = (L + R) // 2\n",
    "            if arr[mid] == mid:\n",
    "                ans = mid\n",
    "                break\n",
    "            elif arr[mid] > mid:\n",
    "                R = mid - 1\n",
    "            else:\n",
    "                L = mid + 1\n",
    "        \n",
    "        if ans == -1:   return -1\n",
    "        while ans > 0 and arr[ans-1] == ans-1:\n",
    "            ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i, x in enumerate(arr):\n",
    "            if i == x:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if (arr[i] == i):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]==i:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        for i in range(n):\n",
    "            if i==arr[i]:\n",
    "                return i\n",
    "                break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        return next((i for i in range(len(arr)) if i == arr[i]), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = len(arr) - 1\n",
    "        tmp = 1000000000000\n",
    "        if len(arr) == 1:\n",
    "            if arr[0] == 0:\n",
    "                return 0\n",
    "            return -1\n",
    "        while i <= j:\n",
    "            zhong = (i + j) // 2\n",
    "            if zhong == arr[zhong]:\n",
    "                if zhong < tmp:\n",
    "                    tmp = zhong\n",
    "                    j = zhong\n",
    "            elif zhong > arr[zhong]:\n",
    "                i = zhong\n",
    "            elif zhong < arr[zhong]:\n",
    "                j = zhong\n",
    "            if i + 1 == j:\n",
    "                if arr[i] == i:\n",
    "                    return i\n",
    "                if arr[j] == j:\n",
    "                    return j\n",
    "                break\n",
    "        if tmp != 1000000000000:\n",
    "            return tmp\n",
    "        return -1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        # return min((i  for i, num in enumerate(arr) if num == i), default=-1)\n",
    "        \n",
    "        left,right = 0,len(arr)-1\n",
    "        m = float('inf')\n",
    "        while left <= right:\n",
    "            middle = left + (right - left)//2\n",
    "            if arr[middle] < middle :\n",
    "                left = middle + 1\n",
    "            elif arr[middle] >= middle:\n",
    "                if arr[middle] == middle:\n",
    "                    m = min(middle,m)\n",
    "                right = middle - 1\n",
    "           \n",
    "        if m != float('inf') :\n",
    "            return m\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] < mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if arr[left] == left else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        return min((i  for i, num in enumerate(arr) if num == i), default=-1)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedPoint(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            cnt = left + right >> 1\n",
    "            print(cnt, left, right)\n",
    "            if arr[cnt] < cnt:\n",
    "                left = cnt + 1\n",
    "            else:\n",
    "                right = cnt \n",
    "        return left if arr[left] == left else -1\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
